In communication environments it is common for a communication medium or external signals to introduce signal errors. Said errors must be detected and, if possible, corrected in reception so that correct data may be recovered. Several techniques exist for error detection and correction in the state of the art, including the codification and decodification of data based on low density parity check codes for correcting errors.
Low density parity check codes (LDPC) are error correction codes that are used in transmitting over noisy transmission channels. These codes introduce a certain redundancy in a message (a larger number of bits is sent than in the original message), but in such a way that at reception it is possible to detect whether there are errors in the message received and to correct the errors.
An LDPC code is a code whose parity matrix is not very dense, that is to say that the majority of its elements are zeros. This type of code was published for the first time at the beginning of the 1960s, by Robert G. Gallagher “Low Density Parity Check Codes,” M.I.T. Press, 1963, and was shown to have features very close to the known Shannon limit (theoretical maximum rate for data transmission). However, with the original definition of the codes and the technology of that time, an attainable implementation of adequate complexity was not possible. Recently, thanks to the evolution of integrated circuits and the invention of structured matrices, these codes are once again of great interest.
In the state of the art there are multiple methods for achieving codification and decodification of errors. Some methods are those published in U.S. Pat. Nos. 7,343,548B2 and 7,203,897B2, both entitled “Method and Apparatus for Encoding and Decoding Data,” each of which outlines methods for improving protection when confronted with errors in data transmission. The invention can also be related to standards IEEE802.16e and 802.11n, which present codification and decodification for reducing errors. In any case, the patents and standards mentioned use the double diagonal structure, which is known in the state of the art, while the structure presented in this document is new and allows an implementation with better features without increasing the level of complexity (thus at lower cost) of protection against errors in communicating data over noisy media. It is known in the state of the art that having columns with a Hamming weight equal to or less than 2 in the parity matrix restricts the features of the LDPCs. However, for reasons of complexity of implementation of the codifier, matrices with a double diagonal section Hb1 have been used in the state of the art. The new structure presented in this document, which adds a third diagonal to the section Hb1 of the binary model matrix, allows the total number of columns in the parity matrix with a Hamming weight less than or equal to 2 to be lower, and thus better features can be achieved. This third diagonal was selected in such a way that the increase in the complexity of implementation of the codifier is practicably negligible.
The documents previously presented do not interfere with the novelty nor the inventive superiority of the present invention. Although they are all based on utilization of the LDPC technology, which is known in the state of the art, the method and device of this document utilizes a type of quasi-cyclic code (Quasi-Cyclic Low Density Parity Check Code, or QC-LDPC), and applies a parity matrix with a different structure as the central point of the invention.
Throughout this document, a specific nomenclature will be employed to differentiate the elements utilized throughout the description of the invention. A bold capital letter (e.g., A) indicates that the element is a matrix; a bold small letter (e.g., a) indicates that the element is a vector, while a small non-bold letter (e.g., a) indicates that the element is a scalar value. On the other hand, scalar elements that comprise a matrix of the size M×N are indicated in the form a(i,j), where the tuple (i,j) is the position of said element within the matrix, with 0≦i≦M−1 being the row number and 0≦j≦N−1 the column number. The elements that comprise a vector of size M are annotated in the form a(i), with (i) being the position of the element in the vector (0≦i≦M−1).
Also, throughout the invention the term “cyclical rotation” will be used, which will be defined below. A cyclical rotation z on a vector a=[a(0), a(1), . . . , a(M−2), a(M−1)] consists in cyclically rotating its elements toward the right, obtaining the vector [a((M−z)%M), . . . , a((M−z−1)%M)] as the result, with % being the “module” operator. In the same way, a cyclical rotation z applied over a matrix A=[a(0), . . . , a(N−1)] operates on its columns, obtaining the matrix [a((N−z)%N), . . . , a((N−z−1)%N)] as the result. A cyclical rotation can also be defined in the opposite direction (toward the left) so that a cyclical rotation z toward the right is equivalent to a cyclical rotation M−z and N−z respectively for vector and matrix toward the left.